//https://leetcode.cn/problems/product-of-array-except-self/?envType=study-plan-v2&envId=top-100-liked
//除自身以外数组的乘积:https://blog.csdn.net/h799710/article/details/106569682
//前缀与后缀乘积相乘；

#include <vector>
#include <stack>
#include <list>
#include <map>
#include <string>
#include <unordered_map>
#include <algorithm>

using namespace std;


vector<int> productExceptSelf(vector<int>& nums) {
    int len = nums.size();
    vector<int > res(len, 1);
    vector<int > left(len, 1);
    vector<int > right(len, 1);
    for (int i = 1; i < len; i++) {
        //注：arr[0] 没有前缀乘积默认为1， arr[len-1] 没有后缀乘积， 默认为1
        left[i] = left[i - 1] * nums[i - 1];    //记录每个元素的前缀乘积
        right[len - i - 1] = right[len - i] * nums[len - i];    //记录每个元素的后缀乘积
    }
    for (int i = 0; i < len; i++) {
        res[i] = left[i] * right[i];
    }
    return res;
}